package com.wellsfargo.bm;

public class Sorter {

	int[] A;
	
	private int median(int l,int h){
		int mid = l+(h-l)/2;
		if(A[mid]>=A[h]){
			if(A[mid]<=A[l])
				return A[mid];
			else if(A[h]>A[l])
				return A[h];
		}
		else
		{
			if(A[mid]>=A[l])
				return A[mid];
			else if(A[l]>A[h])
				return A[h];
		}
		return A[l];
	}
	private Point partition(int l, int h){
		Point P = new Point();
		int low=l;
		int mid=l;
		int high=h;
		int pV=median(l,h);
		while(mid<=high){
			if(A[mid]==pV)
				mid++;
			else if(A[mid]<pV){
				swap(low,mid);
				low++;mid++;
			}
			else{
				swap(high,mid);
				high--;
			}
		}
		P.setLow(low-1);
		P.setHigh(high+1);
		return P;
	}
	
	private void swap(int i, int j){
		int temp=A[i];
		A[i]=A[j];
		A[j]=temp;
	}
	
	public void quickSortHelper(int[] a){
		A=a;
		quickSort(0,A.length-1);
	}
	
	private void quickSort(int low, int high){
		if(low>high)
			return;
		Point p= partition(low,high);
		quickSort(low,p.getLow());
		quickSort(p.getHigh(),high);
	}
	public void printArray(){
		for(int i=0;i<A.length;i++)
			System.out.println(A[i]);
	}
}
